L2-052 吉利矩阵

题目 L2-052 吉利矩阵

思路分析

类似于n皇后问题的 从点入手 看每个位置能放什么

代码实现

最淳朴的方式： 4/25

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

int l,n;

int g[5][5];

int ans=0;

bool check(){

	for(int i=0;i<n;i++){

		ll sum_row=0,sum_col=0;

		for(int j=0;j<n;j++){

			sum_row+=g[i][j];

			sum_col+=g[j][i];

		}

		if(sum_col!=l || sum_row!=l)	return false;

	}

	return true;

}

void dfs(int x,int y){

	if(x==n){

		if(check())	ans++;

		return;

	}

	for(int i=0;i<=l;i++){

		g[x][y]=i;

		int nx=x,ny=y+1;

		if(ny==n)	nx++,ny=0;

		dfs(nx,ny);

	}

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>l>>n;

	dfs(0,0);

	cout<<ans;

	return 0;

}

剪枝 将每行每列的值作为参数传入 如果超过l立刻剪枝

23/25

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};

const int inf = 0x3f3f3f3f;

int l,n;

int g[5][5];

ll ans=0;

void dfs(int x,int y,vector<ll>& sum_row,vector<ll>& sum_col){

	if(x==n){

		for(int i=0;i<n;i++){

			if(sum_row[i]!=l || sum_col[i]!=l)	return;

		}

		ans++;

		return;

	}

	for(int i=0;i<=l;i++){

		if(sum_row[x]+i>l || sum_col[y]+i>l)	break;

		int nx=x,ny=y+1;

		if(ny==n)	nx++,ny=0;

		g[x][y]=i;

		sum_row[x]+=i;

		sum_col[y]+=i;

		dfs(nx,ny,sum_row,sum_col);

		sum_row[x]-=i;

		sum_col[y]-=i;

	}

}

int main() {

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>l>>n;

	vector<ll> sum_row(n,0),sum_col(n,0);

	dfs(0,0,sum_row,sum_col);

	cout<<ans;

	return 0;

}

同类题型

视频讲解

⬅️ L2-051 满树的遍历 🏠 00-天梯赛